ユークリッドの互除法 (Euclidean Algorithm)
ユークリッドの互除法
ユークリッドの互除法とは、2つの整数a, bの最大公約数gcd(a, b)を効率よく求めるアルゴリズム。
gcd(72, 27)に関して、
72 / 27 = 2 amari 18
27 / 18 = 1 amari 9
18 / 9 = 2
割り切れたので、gcd(72, 27) = 9。
つまり、
$ gcd(72, 27) = gcd(72 mod 27, 27) = gcd(18, 27) = gcd(18, 27 mod 18) = gcd(18, 9) = gcd(18 mod 9, 9) = gcd(0, 9) = 9
計算量において、素因数分解で求めるとO(p)必要なのに対し、ユークリッドの互除法だとO(log(p))。
拡張ユークリッドの互除法 ( Extended Euclidean Algorithm)
一次不定方程式$ ax + by = cの整数解を求める。
一般のsに対して整数a,bを具体的に計算することで$ ar_0 + br_1 = gcd(r_0, r_1) とできる。
RSA暗号の鍵生成・楕円曲線暗号やエルガマル暗号の有限体の除算に利用される。
フェルマーの小定理 (Fermat's little theorem)
有限体$ F_p^*の元$ x対して、$ x^{p-1} = 1
よって、$ x^{p-2}が$ xの逆数